package 链表;

import java.util.LinkedHashSet;
import java.util.Set;

/**
 * <p>
 * https://leetcode-cn.com/problems/linked-list-cycle/
 * 给定一个链表，判断链表中是否有环。
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
 * 输入：head = [3,2,0,-4], pos = 1
 * 输出：true
 * 解释：链表中有一个环，其尾部连接到第二个节点。
 * </p>
 *
 * @author AJun
 * @since 2020/8/12
 */
public class _141_环形链表 {

    /**
     * hash 表
     */
    public boolean hashSolution(ListNode head) {
        Set<ListNode> set = new LinkedHashSet<>(); // 有序且值不重复
        while (head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

    /**
     * 快慢指针
     */
    public boolean slowAndFastSolution(ListNode head) {
        if (head == null)
            return false;

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            if (slow.equals(fast))
                return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

    /**
     * 快慢指针异常版
     */
    public boolean slowAndFastExceptionSolution(ListNode head) {
        try {
            ListNode slow = head;
            ListNode fast = head.next;
            while (!slow.equals(fast)) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return true;
        } catch (Exception e) {
            return false;
        }
    }

    /**
     * 递归: 破坏链表结构
     */
    private boolean traverseBreakSolution(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        // 判断是否是自环状态
        if (head == head.next) {
            return true;
        }
        // 让遍历过的节点自环
        ListNode breaker = head.next;
        head.next = head;
        return traverseBreakSolution(breaker);
    }

    /**
     * 递归: 标记法
     */
    private boolean traverseMarkSolution(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.val == 0xcafebabe) {
            return true;
        }
        head.val = 0xcafebabe;
        return traverseMarkSolution(head.next);
    }

}
